

#ifndef __ALGORITHM_H__
#define __ALGORITHM_H__

template<class T>
void Swap(T &a, T &b)
{
	T temp = a;
	a = b;
	b = temp;
}

/*
	insertion sort
*/
template<class T>
void InsertSort(T elem[], int n)
{
	for(int i = 1; i < n; ++i)
	{
		for(int j = i; j > 0 && elem[j] < elem[j - 1]; --j)
		{
			swap(elem[j], elem[j - 1]);
		}
	}
}

/*
	selectin sort
*/
// simple selection sort
template<class T>
void SimpleSelectionSort(T elem[], int n)
{
	for(int i = 0; i < n - 1; ++i)
	{
		int lowIndex = i;
		for(int j = i + 1; j < n; ++j)
		{
			if(elem[j] < elem[lowIndex])
				lowIndex = j;
		}
		Swap(elem[i], elem[lowIndex]);
	}
}

//heap sort
template<class T>
void SiftAdjust(T elem[], int low, int high)
{
	for(int f = low, i = 2 * low + 1; i <= high; i = 2 * i + 1)
	{
		if(i < high && elem[i] < elem[i + 1])
			i++;
		if(elem[f] > elem[i])
			break;
		Swap(elem[f], elem[i]);
		f = i;
	}
}
template<class T>
void HeapSort(T elem[], int n)
{
	int i;
	for(i = (n-2)/2; i >= 0; --i)
	{
		SiftAdjust(elem, i, n - 1);
	}
	for(i = n - 1; i > 0; --i)
	{
		Swap(elem[0], elem[i]);
		SiftAdjust(elem, 0, i - 1);
	}
}

#endif